
import java.util.ArrayList;
import java.util.Random;


// StudentMazeSolver.java
//
// ICS 23 Summer 2004
// Project #1: Dark at the End of the Tunnel


// The StudentMazeSolver class is where you will implement your maze
// solving algorithm.  Presently, it returns a newly-created solution,
// which contains only the starting position and nothing else.

public class StudentMazeSolver
implements MazeSolver
{
	private enum Direction {
		EAST, NORTH, SOUTH, WEST
	}
	private ArrayList<Direction> getPossibleMoves(int a_x, int a_y, boolean[][] a_visited, Maze a_maze) {

		ArrayList<Direction> neighbors = new ArrayList<Direction>();

		System.out.println("curX | curY : " + a_x + " " + a_y);
		if (a_maze.canMoveEastFrom(a_x, a_y) && !a_visited[a_y][a_x+1]){
			neighbors.add(Direction.EAST);
		}
		if (a_maze.canMoveNorthFrom(a_x, a_y) && !a_visited[a_y-1][a_x]){
			neighbors.add(Direction.NORTH);
		}
		if (a_maze.canMoveSouthFrom(a_x, a_y) && !a_visited[a_y+1][a_x]){
			neighbors.add(Direction.SOUTH);
		}
		if (a_maze.canMoveWestFrom(a_x, a_y) && !a_visited[a_y][a_x-1]){
			neighbors.add(Direction.WEST);
		}
		return neighbors;
	}

	public MazeSolution solveMaze(Maze maze, MazeSolverListener listener)
	{
		boolean[][] m_visited = new boolean[maze.getHeight()][maze.getWidth()];
		for(int y = 0; y < maze.getHeight(); ++y){
			for(int x = 0; x < maze.getWidth(); ++x){
				m_visited[y][x] = false;
			}
		}
		MazeSolution sol = MazeSolutionFactory.createMazeSolution(
				maze.getWidth(), maze.getHeight(),
				maze.getStartXPosition(), maze.getStartYPosition(),
				maze.getEndXPosition(), maze.getEndYPosition());
		Random rand = new Random(System.currentTimeMillis());
		listener.startingMazeSolution(sol);
		while(!sol.solutionComplete()){
			m_visited[sol.getLastYPosition()][sol.getLastXPosition()] = true;
			ArrayList<Direction> moves = getPossibleMoves(sol.getLastXPosition(), 
					sol.getLastYPosition(), m_visited, maze);
			Direction randDir = null;
			if(moves.size() > 0){ 
				randDir = moves.get(rand.nextInt(moves.size()));
				switch(randDir){
					case EAST: 	sol.moveEast(); 	break;
					case NORTH: sol.moveNorth(); 	break;
					case SOUTH: sol.moveSouth(); 	break;
					case WEST: 	sol.moveWest(); 	break;
				}
				
			}
			else{
				sol.backUp();
			}
			
			listener.solutionChanged(sol);
		}		
		return sol;
	}
}
